package q450_deleteNode;
import CommonClass.Common.TreeNode;
public class Solution_2 {
    /*
    用迭代的方法也非常类似 注意找到节点后对其左右节点的判空即可
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode pre = null, cur = root;
        while (cur != null && cur.val != key) {
            pre = cur;
            if (cur.val > key) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        if (cur == null) return root;


        // 接下来三个都需要对cur的左右判空
        if (pre == null) {
            if (cur.right != null) {
                TreeNode rightNode = cur.right;
                while (rightNode.left != null) {
                    rightNode = rightNode.left;
                }
                rightNode.left = cur.left;
                return cur.right;
            }else {
                return cur.left;
            }
        }

        if (pre.val > key) {
            if (cur.right != null) {
                TreeNode rightNode = cur.right;
                while (rightNode.left != null) {
                    rightNode = rightNode.left;
                }
                rightNode.left = cur.left;
                pre.left = cur.right;
            }else {
                pre.left = cur.left;
            }

        }else {
            if (cur.right != null) {
                TreeNode rightNode = cur.right;
                while (rightNode.left != null) {
                    rightNode = rightNode.left;
                }
                rightNode.left = cur.left;
                pre.right = cur.right;
            }else {
                pre.right = cur.left;
            }
        }

        return root;
    }
}
